package com.cong.sort.count;

import java.util.Arrays;

/**
 * 计数排序
 * 是非比较排序
 * 适用于特定问题，对数据原有要求
 *复杂读为O(k+n)
 * @author cong
 * <p>
 * created on 2021/3/20 上午11:03
 */
public class CountSort {
    public static void main(String[] args) {
        int[] arr = {4,5,4,6,8,9,7,5,2,3,0,1,1,2,5,4,8,9,6,0};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 计数排序
     * @param arr
     * @return
     */
    private static int[] sort(int[] arr) {
        //等长数组保存排序结果
        int[] result = new int[arr.length];
        //10个类别0~9
        int[] count = new int[10];

        /**
         * 将原数组元素作为索引下标，出现的次数作为元素
         */
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        //[2, 2, 2, 1, 3, 3, 2, 1, 2, 2]
        System.out.println(Arrays.toString(count));
//        for (int i = 0,j=0; i < count.length; i++) {
//            while (count[i]-->0)result[j++]=i;
//        }
        //累加数组
        //[2, 4, 6, 7, 10, 13, 15, 16, 18, 20]
        for (int i = 1; i < count.length; i++) {
            count[i]=count[i]+count[i-1];
        }
        System.out.println(Arrays.toString(count));
       //对arr原数组进行倒叙
        for (int i = arr.length-1; i >=0 ; i--) {
            //第一次arr[19]=0;cout[0]=2;--后为1,这个0是第二个0,位置没有改变，所以是稳定的
            //索引1的元素为0
            result[--count[arr[i]]]=arr[i];
        }

        return result;
    }
    /**
     * 计数排序
     * @param arr
     * @return
     */
    private static int[] sort2(int[] arr) {
        //等长数组保存排序结果
        int[] result = new int[arr.length];
        //10个类别0~9
        int[] count = new int[10];

        /**
         * 将原数组元素作为索引下标，出现的次数作为元素
         */
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        for (int i = 0,j=0; i < count.length; i++) {
            while (count[i]-->0)result[j++]=i;
        }
        return result;
    }


}
